# 栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表
# 栈的特点：后进先出LIFO(last-in first-out)
# 栈的概念：栈顶和栈底
# 栈的基本操作：
#   进栈(压榨) push
#   出栈：pop
#   取栈顶：gettop
# 实现方式 用列表自己封装Stack
# 为什么要有栈 因为时间复杂度为O(1)
class Stack:
    def __init__(self):
        self.stack = []

    def push(self, element):
        self.stack.append(element)

    def pop(self):
        if len(self.stack) == 0:
            return None
        else:
            return self.stack.pop()

    def is_empty(self):
        return self.stack == []

    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None

    def get_stack(self):
        return self.stack


stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.get_stack())


# 栈的实际应用 括号匹配问题：给一个字符串，其中包含小括号，中括号，大括号，求该字符串中的括号是否匹配.
# 例如()()[]{}匹配
# ([{()}])匹配
# [](不匹配
# [(])不匹配
def check_symbol(str1):
    s = Stack()
    print(str1)
    for x in str1:
        if x == '(' or x == '[' or x == '{':
            s.push(x)
        else:
            if s.is_empty():
                return False
            elif (s.get_top() == '(' and x == ')') or (s.get_top() == '[' and x == ']') or (
                    s.get_top() == '{' and x == '}'):
                s.pop()
            else:
                return False
    if s.is_empty():
        return True
    else:
        return False


print(check_symbol('[]({[]}){}'))
